1.69

题目

Let $Σ = {0, 1}$ . Let

W W_{k} = {w w ∣ w \in Σ^{*} and w is of length k} .

a. Show that for each $k$ , no DFA can recognize $W W_{k}$ with fewer than $2^{k}$ states.

b. Describe a much smaller NFA for $\overset{―}{W W_{k}}$ , the complement of $W W_{k}$ .

思路

点击展开

a. Myhill–Nerode theorem 秒杀

b. NFA 刻画可能性，善于直接刻画存在性问题
$W W_{k}$ 的故事是：对任意 $m \leq k$ ，第 $m$ 位和第 $m + k$ 位是相同字符
$\overset{―}{W W_{k}}$ 的故事是：存在 $m \leq k$ ，第 $m$ 位和第 $m + k$ 位不同（或字符串长度不是 $2 k$ ）
所以我们为每个 $m$ 设计一个通道，第 $m$ 位和第 $m + k$ 位不同时能够通向接受状态

解答

点击展开

a. ${w ∣ w \in Σ^{*} and w is of length k}$ is pairwise distinguishable by L

b. 当 $k = 3$ 时，构造 NFA 如下图：

NFA_1.69.jpg

$q_{0}$ 是起始状态，黑圈代表拒绝状态，红圈代表接受状态。这里将本质不同的接受方式分开，稍作化简可得下图：

NFA_1.69_simplified.jpg

一般地，需要至多 $2 k^{2} + k + 2$ 个状态，这远小于 $2^{k}$